using System.Linq;
using System.Numerics;
using System.Collections.Generic;

//n=m1*m2 ,where gcd(m1,m2)=1
(int,int) DecomposeIntoCoprimes(int n)
{
    List<int> factors = GetFactors(n);
    List<(int,int)> pairs =[];
    foreach(int f in factors)
    {
        if(f==1) continue;
        int m = n/f;
        if(GCD(f,m)==1)
            pairs.Add((f,m));
    }
    return pairs.OrderBy(x=>x.Item1+x.Item2).First();
}

int GCD(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int LCM(int a, int b)
{
    return Math.Abs(a * b) / GCD(a, b);
}

//欧拉函数
int Phi(int n)
{
    int result = n;
    for (int p = 2; p * p <= n; p++)
    {
        if (n % p == 0)
        {
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}
//因数分解
List<int> GetFactors(int n)
{
    List<int> factors = [];
    for (int i = 1; i <= Math.Sqrt(n); i++)
    {
        if (n % i == 0)
        {
            factors.Add(i);
            if (i != n / i)
                factors.Add(n / i);
        }
    }
    factors.Sort();
    return factors;
}

int test(int n, int mod,IEnumerable<int> list){
    foreach(int i in list.OrderBy(x=>x)){
        var res =BigInteger.ModPow(n,i,mod);
        Console.WriteLine($"{n}^{i} mod {mod} = {res}");
        if(res==1){
            Console.WriteLine($"ord_{mod}({n}) = {i}");
            return i;
        }
    }
    return -1;
}
//求n对模mod的阶 带过程
int ord_mini(int n,int mod){
    if(mod==1) return 1;
    int phi = Phi(mod);
    Console.WriteLine($"phi({mod}) = {phi}");
    List<int> factors = GetFactors(phi);
    factors.Remove(1);
    Console.WriteLine($"factors of phi({mod}) = {string.Join(",",factors)}");
    return test(n,mod,factors);
}

//适用于大数的分解求阶 带过程
int ord(int n,int mod){
    (int m1,int m2) = DecomposeIntoCoprimes(mod);
    Console.WriteLine($"mod = {mod} = {m1}*{m2}");
    int ord1 = ord_mini(n,m1);
    int ord2 = ord_mini(n,m2);
    int ord = LCM(ord1,ord2);
    Console.WriteLine($"ord_{mod}({n}) = [ord_{m1}({n}),ord_{m2}({n})] = {ord}");
    return ord;
}

//n的简化剩余系
IEnumerable<int> simpleRest(int n){
    return Enumerable.Range(1,n).Where(x=>GCD(x,n)==1);
}

//求n对模mod的阶 仅数值
int ord_value(int n,int mod){
    if(mod==1) return 1;
    int phi = Phi(mod);
    return GetFactors(phi).First(x=>(BigInteger.ModPow(n,x,mod))==1);
}

//求mod的原根
IEnumerable<int> oriRoot(int mod){
    var rest= simpleRest(mod);
    var phi = Phi(mod);
    return rest.Where(x=>ord_value(x,mod)==phi);
}

//mod，以g为底n的离散对数
int index(int mod,int g,int n){
    return Enumerable.Range(0,mod).First(x=>BigInteger.ModPow(g,x,mod)==n);
}